package com.dragon.datastructure.sort;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author dragon
 * @since 2020/1/7
 */
public class HeapSort {


    /**
     * 堆化
     *
     * @param array 需要heapify的元素
     */
    private static void heapify(int[] array) {
        for (int i = parentIndex(array.length - 1); i >= 0; i--) {
            siftDown(array, i);
        }
    }

    public static int[] sort(int[] array) {
        if (array == null || array.length < 2) {
            return array;
        }
        int[] result = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            heapify(array);
            result[i] = array[0];
            array[0] = array[array.length - 1];
        }

        return result;

    }

    public static void main(String[] args) {
        int[] array = {90, 24, 2, 11, 1, 2, 9, 1};
        System.out.println(Arrays.toString(sort(array)));
    }

    /**
     * 通过一个节点找到父节点
     *
     * @param index
     * @return
     */
    private static int parentIndex(int index) {
        return (index - 1) / 2;
    }

    private static void siftDown(int[] array, int parentIndex) {
        int leftIndex = parentIndex * 2 + 1;
        while (leftIndex < array.length) {
            int j = leftIndex;
            if (leftIndex + 1 < array.length && array[leftIndex] < array[leftIndex + 1]) {
                j++;
            }
            if (array[j] <= array[parentIndex]) {
                break;
            }
            int tmp = array[parentIndex];
            array[parentIndex] = array[j];
            array[j] = tmp;
        }
    }
}
